package 力扣.双指针.定长区间;

import java.awt.image.Kernel;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class 串联所有单词的子串30 {
    public List<Integer> findSubstring(String s, String[] words) {
        if (s == null || s.length() == 0 || words == null || words.length == 0){
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        Counter3 counter1 = new Counter3();
        for (String word:words) {
            counter1.add(word, 1);
        }
        final int N1 = s.length();
        final int N2 = words[0].length();//每个单词的长度
        final int N3 = words.length;
        for (int i = 0; i < N2; i ++) {
            int left = i;
            int eqNum = 0;
            int counter = 0;//当前窗口的大小
            Counter3 counter2 = new Counter3();
            for (int j = i; j + N2 <= N1 ; j += N2) {
                String teS = s.substring(j,j+N2);
                counter2.add(teS, 1);
                if (counter1.get(teS) == counter2.get(teS)){
                    eqNum++;
                }
                counter++;
                //当前窗口长度小于目标窗口
                if (counter < N3){continue;}

                //窗口已经固定
                if (eqNum == counter1.size()){
                    ans.add(left);
                }

                //窗口滑动
                String des = s.substring(left, left+N2);
                left += N2;//移动左指针，以保证下次的窗口大小不变
                if (counter1.get(des) == counter2.get(des)){
                    eqNum--;
                }
                counter2.add(des, -1);
            }
        }
        return ans;
    }
    class Counter3 extends HashMap<String,Integer> {
        public int get(String key){
            return containsKey(key) ? super.get(key): 0;
        }
        public void add(String key,Integer value){
            put(key, get(key) + value);
            if (get(key) <= 0){
                remove(key);
            }
        }
    }
}
